package vernhe;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E> {
    protected int size;
    protected Node<E> root;

    public int size(){
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTowChildren() {
            return left != null && right != null;
        }

        /**
         * 是父节点的左节点
         * @return
         */
        public boolean isLeft() {
            return (parent != null) && this == parent.left;
        }

        /**
         * 是父节点的右节点
         * @return
         */
        public boolean isRight() {
            return (parent != null) && this == parent.right;
        }

        /**
         * 得到兄弟节点
         */
        public Node<E> sibling() {
            if (isLeft()) {
                return parent.right;
            }
            if (isRight()) {
                return parent.left;
            }
            return null;
        }
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root,visitor);
    }


    public void inorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorder(root,visitor);
    }

    public void postorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        postorder(root,visitor);
    }

    /**
     * 得到传入节点的前驱节点(中序遍历时的前一个节点)
     * @param node
     * @return
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        //如果左子树不为空，则在左子树中查找
        Node<E> left = node.left;
        if (left != null) {
            while (left.right != null) {
                left = left.right;
            }
            return left;
        }

        //如果左子树为空，则向上查找父节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

//        node.parent == null;  return null
//        node == node.parent.right;  return node.parent
        return node.parent;
    }

    /**
     * 得到传入节点的后继节点，与得到前驱节点的方法对称
     * @param node
     * @return
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;

        //如果右子树不为空，则对其进行查找
        Node<E> right = node.right;
        if (right != null) {
            while (right.left != null) {
                right = right.left;
            }
            return right;
        }

        //如果由子树为空，则向上查找父节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

//        node.parent == null;  return null
//        node == node.parent.left;  return node.parent
        return node.parent;
    }

    /**
     * 调试使用，用于查看树的信息
     */
    public void printInfo() {
        levelOrderTraversal();
    }

    /**
     * 前序遍历
     * @param node
     * @param visitor
     */
    private void preorder(Node<E> node, Visitor visitor) {

        visitor.visit(node.element);
        if (node.left!= null) preorder(node.left,visitor);
        if (node.right!= null) preorder(node.right,visitor);
    }

    /**
     * 中序遍历
     * @param node
     * @param visitor
     */
    private void inorder(Node<E> node, Visitor visitor) {
        if (node.left!= null) inorder(node.left,visitor);
        visitor.visit(node.element);
        if (node.right!= null) inorder(node.right,visitor);
    }

    /**
     * 后序遍历
     * @param node
     * @param visitor
     */
    private void postorder(Node<E> node, Visitor<E> visitor) {
        if (node.left!= null) postorder(node.left,visitor);
        if (node.right!= null) postorder(node.right,visitor);
        visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    private void levelOrderTraversal() {
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.println(temp.element);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 层次遍历，对外提供Visitor接口
     * @param visotor
     */
    public void levelOrder(Visitor visotor) {
        if (root == null || visotor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            visotor.visit(temp.element);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 判断是否为完全二叉树
     */
    public boolean isComplete() {
        if (root == null) return false;
        boolean sholdBeLeafNode = false;
        Queue<Node<E>> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null){
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                sholdBeLeafNode = true;
            }
        }
        return true;
    }

    /**
     * 得到树的高度
     * @return
     */
    public int height() {
        //return height1(root);
        return height2();
    }

    /**
     * 递归得到树的高度
     * @param node
     * @return
     */
    private int height1(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height1(node.left),height1(node.right));
    }

    /**
     * 非递归得到树的高度
     * 层次遍历
     * @return
     */
    private int height2() {
        if (root == null) return 0;

        //记录层数
        int levleSize = 0;
        //记录每一层的节点数量
        int rowSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            //每弹出一个元素，这一行的元素个数减一
            rowSize--;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            //当这一行的元素个数为0的时候，说明当前层已经遍历完，层次加一，并更新下一层的rowSize
            if (rowSize == 0) {
                levleSize++;
                rowSize = queue.size();
            }
        }
        return levleSize;
    }

    /**
     * 对子类提供一个创建节点的接口
     * @param element
     * @param parent
     * @return
     */
    protected Node<E> createNode(E element,Node<E> parent) {
        //默认传入普通的Node
        return new Node<>(element,parent);
    }

    public static interface Visitor<E> {
        void visit(E element);
    }

}
